这道题没有太多可说的,属于基本题的扩展。
可以先参考前面的 12. Remove Duplicates from Sorted List.
而这道题多出的一点把戏在于,要把重复的数据删的干干净净。我的策略很简单,将重复的数据做一个标记,isDuplicate,
然后再删掉重复元素的基础上,最后给剩下那个光棍补上一刀。
虽然有点啰嗦,但是效率还过得去。
#include <cstddef>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if (head == NULL) return head;
ListNode preHead(0);
preHead.next = head;
ListNode *pre = &preHead;
bool isDuplicate = false;
ListNode *p = head;
while (p->next)
if (p->val == p->next->val) {
ListNode *next = p->next->next;
delete p->next;
p->next = next;
isDuplicate = true;
} else if (isDuplicate) {
ListNode *next = p->next;
delete p;
p = next;
pre->next = p;
isDuplicate = false;
} else {
pre = p;
p = p->next;
}
if (isDuplicate) {
ListNode *next = p->next;
delete p;
pre->next = next;
}
return preHead.next;
}
};